#include "main/utils.h"
using namespace std;

// **************solution1****************
int helper1(const vector<int>& nums, int idx) {
  if (idx == 0) {
    return nums[0];
  } else if (idx == 1) {
    return max(nums[0], nums[1]);
  }
  return max(helper1(nums, idx - 1), helper1(nums, idx - 2) + nums[idx]);
}

int rob1(const vector<int>& nums) {
  if (nums.empty()) {
    return 0;
  }
  return helper1(nums, nums.size() - 1);
}

// **************solution2****************
void helper2(const vector<int>& nums, vector<int>& dp, int idx) {
  if (idx == 0) {
    dp[0] = nums[0];
  } else if (idx == 1) {
    dp[1] = max(nums[0], nums[1]);
  } else if (dp[idx] == -1) {
    helper2(nums, dp, idx - 1);
    helper2(nums, dp, idx - 2);
    dp[idx] = max(dp[idx - 1], dp[idx - 2] + nums[idx]);
  }
}

int rob2(const vector<int>& nums) {
  int size = nums.size();
  if (size == 0) {
    return 0;
  }
  vector<int> dp(size, -1);
  helper2(nums, dp, size - 1);
  return dp[size - 1];
}

// **************solution3****************
int rob3(const vector<int>& nums) {
  int size = nums.size();
  if (size == 0) {
    return 0;
  }
  vector<int> dp(size, -1);
  for (int i = 0; i < size; ++i) {
    if (i == 0) {
      dp[0] = nums[0];
    } else if (i == 1) {
      dp[1] = max(nums[0], nums[1]);
    } else {
      dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
    }
  }
  return dp[size - 1];
}

// **************solution4****************
int rob4(const vector<int>& nums) {
  int size = nums.size();
  if (size == 0) {
    return size;
  }
  vector<int> dp;
  dp.push_back(nums[0]);
  dp.push_back(max(nums[0], nums[1]));
  for (int i = 2; i < size; ++i) {
    dp[i % 2] = max(dp[(i - 1) % 2], dp[(i - 2) % 2] + nums[i]);
  }
  return dp[(size - 1) % 2];
}

// **************solution5****************
int rob5(const vector<int>& nums) {
  int size = nums.size();
  if (size == 0) {
    return 0;
  }
  int dp[2][2];
  dp[0][0] = 0;
  dp[1][0] = nums[0];
  for (int i = 1; i < size; ++i) {
    dp[0][i % 2] = max(dp[0][(i - 1) % 2], dp[1][(i - 1) % 2]);
    dp[1][i % 2] = dp[0][(i - 1) % 2] + nums[i];
  }
  return max(dp[0][(size - 1) % 2], dp[1][(size - 1) % 2]);
}


int main() {
  vector<int> nums = {2, 3, 4, 5, 3};
  cout << rob1(nums) << endl;
  cout << rob2(nums) << endl;
  cout << rob3(nums) << endl;
  cout << rob4(nums) << endl;
  cout << rob5(nums) << endl;

  return 0;
}
